#include <iostream>

using namespace std;

struct Node {
    int _key;
    int _priority;
    Node* _left;
    Node* _right;
    int _number;

    Node(int key, int priority) : _key(key), _priority(priority), _left(NULL), _right(NULL), _number(0) {
    }
};

int getNumber(const Node* node) {
    return (node == NULL) ? 0 : node->_number;
}

Node* merge (Node* l, Node* r) {
    if (l == NULL) 
        return r;
    if (r == NULL)
        return l;

    if (l->_priority > r->_priority) {
        l->_right = merge(l->_right, r);  
        l->_number = getNumber(l->_left) + getNumber(l->_right) + 1;
        return l;
    } else {
        r->_left = merge(l, r->_left);
        r->_number = getNumber(r->_left) + getNumber(r->_right) + 1;
        return r;
    }
}

void split(Node* t, int key, Node** l, Node** r) {
    if (t == NULL) {
        *l = NULL;
        *r = NULL;
        return;
    }

    if (t->_key < key) {
        *l = t;
        split(t->_right, key, &((*l)->_right), r);
        (*l)->_number = getNumber((*l)->_left) + getNumber((*l)->_right) + 1;
    } else {
        *r = t;
        split(t->_left, key, l, &((*r)->_left));
        (*r)->_number = getNumber((*r)->_left) + getNumber((*r)->_right) + 1;
    }
}

void push(Node** root, Node* x) {
	if (*root == NULL) {
		*root = x;
		return;
	}
	Node* l = NULL;
	Node* r = NULL;
	split(*root, x->_key, &l, &r);
	*root = merge(merge(l, x), r);
}

void pop(Node** root, int key) {
	Node* lWithoutKeyK = NULL;
	Node* rWithKeyK = NULL;
	Node* lWithKeyK = NULL;
	Node* rWithoutKeyK = NULL;

	split(*root, key - 1, &lWithoutKeyK, &rWithKeyK);
	split(rWithKeyK, key, &lWithKeyK, &rWithoutKeyK);
	*root = merge(lWithoutKeyK, rWithoutKeyK);
}

void printKey(const Node* tree) {
    if (tree == NULL) {
        cout << "null ";
        return;
    }
    printKey(tree->_left);
    cout << tree->_key << " ";
    printKey(tree->_right);
}

void printKeys(const Node* tree) {
    printKey(tree);
    cout << endl;
}

int getKthOrderStatistic(int k, Node* root) {
    Node* iterator = root;
    int iteratorNumber;
    while (iterator != NULL) {
        iteratorNumber = getNumber(iterator->_left);
        if (k == iteratorNumber)
            return iterator->_key;
        else if (k < iteratorNumber) {
            iterator = iterator->_left;
        }
        else {
            k -= getNumber(iterator->_left) + 1;
            iterator = iterator->_right;
        }
    }
    throw "Null Node";
}

int main() {
    Node* newNode = new Node(11, 7);
    for (int i = 0; i < 7; ++i)
        push(&newNode, new Node(i+2, i%5));
    push(&newNode, new Node(17, 5));
    push(&newNode, new Node(25, 5));
    push(&newNode, new Node(26, 5));
    push(&newNode, new Node(28, 5));
    push(&newNode, new Node(19, 5));
    pop(&newNode, 6);
    pop(&newNode, 5);
    push(&newNode, new Node(21, 5));
    printKeys(newNode);

    for (int i = 0; i < 12; ++i)
        cout << getKthOrderStatistic(i, newNode) << endl;
    return 0;
}